package 动态规划;

public class 背包问题 {
	public static void main(String[] args) {
		int[] values = new int[]{6, 3, 5, 4, 6};
		int[] weights = new int[]{2, 2, 6, 5, 4};
		int capacity = 100;
		System.out.println(maxValue2(values, weights, capacity));
		
	}
	
	/**
	 * dp(i, j)表示最大承重为j, 有前i件物品可供选择时的最大价值
	 * dp(0, j) = 0, dp(i, 0) = 0;
	 * if(j < weights[i - 1]) dp(i, j) = dp(i - 1, j)	最后一件物品不选
	 * else dp(i, j) = max(dp(i - 1, j), values[i - 1] + dp(i  1, j - weights[i - 1])); 选择最后一件物品
	 */
	public static int maxValue(int[] values, int[] weights, int capacity) {
		if (values == null || values.length == 0
				|| weights == null || weights.length == 0
				|| values.length != weights.length
				|| capacity <= 0) return 0;
		int[][] dp = new int[values.length + 1][capacity + 1];
		for (int i = 1; i <= values.length; i++) {
			for (int j = 1; j <= capacity; j++) {
				if (j < weights[i - 1]) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
				}
			}
		}
		return dp[values.length][capacity];
	}
	
	/**
	 * 优化: 使用一维数组
	 */
	public static int maxValue1(int[] values, int[] weights, int capacity) {
		if (values == null || values.length == 0
				|| weights == null || weights.length == 0
				|| values.length != weights.length
				|| capacity <= 0) return 0;
		int[] dp = new int[capacity + 1];
		for (int i = 1; i <= values.length; i++) {
			for (int j = capacity; j >= weights[i - 1]; j--) {
				dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
			}
		}
		return dp[capacity];
	}
	/**
	 * 0 - 1背包恰好问题
	 */
	public static int maxValue2(int[] values, int[] weights, int capacity) {
		if (values == null || values.length == 0
				|| weights == null || weights.length == 0
				|| values.length != weights.length
				|| capacity <= 0) return 0;
		int[] dp = new int[capacity + 1];
		// 初始化: 将不合理的值设置为负无穷大
		for (int j = 1; j <= capacity; j++) {
			dp[j] = Integer.MIN_VALUE;
		}
		for (int i = 1; i <= values.length; i++) {
			for (int j = capacity; j >= weights[i - 1]; j--) {
				dp[j] = Math.max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
			}
		}
		return dp[capacity] < 0 ? -1 : dp[capacity];
	}
	
	
}
